
//2112.还原原数组
class Solution {
public:
    vector<int> recoverArray(vector<int>& nums) {
        //lower[i]+k==arr[i]==heigher[i]-k
        //将数组进行排序后,lower[0]一定是nums[0],但是heigher[0]不确定,所以可以枚举nums[i]作为heigher[0]
        int n=nums.size();
        sort(nums.begin(),nums.end());
        
        if(nums[0]==nums[n-1]) 
            return vector<int>(n/2,nums[0]); //如果数组中的值全部相等就可以直接将数组进行返回

        for(int i=1;i<=n/2;i++)
        {
            if((nums[i]-nums[0])%2==1||(nums[i]-nums[0])==0) continue;
            vector<bool> vis(n,false);  //保存那些值是heigher数组中的
            vector<int> ret;
            int prev=0,cur=i,k=(nums[i]-nums[0])/2;
            while(cur<n)
            {   
                if(nums[cur]-nums[prev]<2*k) cur++;
                else if(nums[cur]-nums[prev]>2*k) break;  //当出现大于的情况就不可能再有满足条件的值了
                else 
                {
                    vis[cur]=true;    //将该位置记录为heigher数组的，防止lower数组进行访问
                    ret.push_back(nums[cur]-k);    
                    cur++,prev++;
                    while(prev<cur&&vis[prev]==true) prev++;  //找到lower数组的下一个位置
                }
            }
            if(ret.size()==n/2) return ret;
        }
        return {};
    }
};